﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <climits>
#include <queue>
using namespace std;

//class Solution
//{
//public:
//    void moveZeroes(vector<int>& nums)
//    {
//        if (nums.size() == 1 && nums[0] == 0) return;
//        int a = 0, b = 1, n = nums.size();
//        while (a < n && b < n)
//        {
//            if (nums[a] == 0 && nums[b] != 0)
//            {
//                swap(nums[a], nums[b]);
//                a++;
//                b++;
//            }
//            else if (nums[a] == 0 && nums[b] == 0)
//            {
//                b++;
//            }
//            else if (nums[a] != 0 && nums[b] == 0)
//            {
//                a++;
//                b++;
//            }
//            else
//            {
//                a++;
//                b++;
//            }
//        }
//    }
//};
//
//int main()
//{
//    vector<int> v = { 0,1,0,3,12 };
//    Solution().moveZeroes(v);
//    for (auto e : v)
//        cout << e << endl;
//}




//class Solution
//{
//public:
//    int longestOnes(vector<int>& nums, int k)
//    {
//        int len = 0;
//        for (int l = 0, r = 0; r < nums.size();)
//        {
//            int kk = k;
//            while (kk)
//            {
//                if (nums[r] == 1)    r++;
//                else if (nums[r] == 0)
//                {
//                    kk--;
//                    if (kk == 0) break;
//                    r++;
//                }
//            }
//            len = max(len, r - l + 1);
//            if (r == nums.size() - 1) return len;
//            r++;
//            l = r;
//        }
//        return len;
//    }
//};



//class Solution
//{
//public:
//    int totalFruit(vector<int>& arr)
//    {
//        int hash[100000];
//        int len = 0, kindsum = 0;
//        for (int l = 0, r = 0; r < arr.size(); r++)
//        {
//            if (hash[arr[r]] == 0)
//                kindsum++;
//            hash[arr[r]]++;
//            while (kindsum > 2)
//            {
//                hash[arr[l]]--;
//                if (hash[arr[l]] == 0)
//                    kindsum--;
//                l++;
//            }
//            len = max(len, r - l + 1);
//        }
//        return len;
//    }
//};



//class Solution {
//public:
//    bool equelhash(unordered_map<char, int> hash1, unordered_map<char, int> hash2)
//    {
//        // 首先比较两个哈希表的大小  
//        if (hash1.size() != hash2.size()) {
//            return false;
//        }
//
//        // 遍历第一个哈希表，检查每个键值对是否在第二个哈希表中存在且值相等  
//        for (const auto& pair : hash1) {
//            const char& key = pair.first;
//            const int& value = pair.second;
//
//            // 如果第二个哈希表中没有这个键，或者值不相等，则两个哈希表不相等  
//            auto it = hash2.find(key);
//            if (it == hash2.end() || it->second != value) {
//                return false;
//            }
//        }
//
//        // 如果所有检查都通过，则两个哈希表相等  
//        return true;
//    }
//
//    vector<int> findAnagrams(string s, string p)
//    {
//        unordered_map<char, int> hash1;
//        unordered_map<char, int> hash2;
//        vector<int> ret;
//        for (auto e : p)
//        {
//            hash1[e]++;
//        }
//        int index = 0;
//        for (int l = 0, r = 0; r < s.size(); r++)
//        {
//            hash2[s[r]]++;
//
//            if ((r - l + 1) > p.size())
//            {
//                hash2[s[l]]--;
//                l++;
//            }
//
//            if (equelhash(hash1, hash2))
//                ret.push_back(l);
//        }
//        return ret;
//    }
//    
//};



//int main()
//{
//    string s = "cbaebacd", p = "abc";
//    vector<int> ret = Solution().findAnagrams(s,p);
//    for (auto e : ret)
//        cout << e << endl;
//}


//int main()
//{
//	string s = "barfoo";
//	string ret = s.substr(1, 3);
//	cout << ret;
//}





//class Solution
//{
//public:
//    int pivotIndex(vector<int>& nums)
//    {
//        int n = nums.size();
//        //初始化dp数组
//        vector<int> dp(n + 1);
//        for (int i = 1; i <= n; i++)
//            dp[i] = dp[i - 1] + nums[i];
//        //使用dp数组
//        for (int i = 1; i <= n; i++)
//        {
//            if (dp[i - 1] == (dp[n - 1] - dp[i]))
//                return i;
//        }
//        return -1;
//    }
//};
//
//
//int main(){
//    vector<int> nums = { 1, 7, 3, 6, 5, 6 };
//    int ret = Solution().pivotIndex(nums);
//    cout << ret;
//}


//int main()
//{
//    string s;
//    cin >> s;
//
//    for (int i = 0; i < s.size(); i++)
//    {
//        switch (s[i])
//        {
//        case 'a':
//            s[i] = 'A';
//            break;
//        case 'e':
//            s[i] = 'E';
//            break;
//        case 'i':
//            s[i] = 'I';
//            break;
//        case 'o':
//            s[i] = 'O';
//            break;
//        case 'u':
//            s[i] = 'U';
//            break;
//        default:
//            break;
//        }
//
//    }
//
//    for (auto e : s)
//    {
//        cout << e << endl;
//    }
//    return 0;
//}




//int main()
//{
//	double a = 3.14;
//	a *=  pow(2, 100);
//	cout << (unsigned long long)a << endl;
//}




//#define int long long
//signed main()
//{
//    int n;
//    cin >> n;
//
//    vector<int> v(n);
//    for (int i = 0; i < n; i++)
//        cin >> v[i];
//    vector<int> fdp(n);
//    vector<int> bdp(n);
//    //fdp[0] = 0,bdp[n-1] = 0;
//    bdp[n - 1] = 0;
//    for (int i = 1; i < n; i++)
//        fdp[i] = fdp[i - 1] + v[i];
//    for (int j = n - 2; j >= 0; j--)
//        bdp[j] = bdp[j + 1] + v[j + 1];
//
//    int min = LLONG_MAX;
//    for (int i = 0; i < n; i++)
//    {
//        int com = abs(fdp[i] - bdp[i]);
//        if (com < min)
//        {
//            min = com;
//        }
//    }
//    cout << min;
//    return 0;
//}




//#include <set>
////#define int long long
//using namespace std;
//const int maxl = 1e5 + 7;


//signed main()
//{
//    int a[maxl], t[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };//月份
//    set<string> st;//存日期
//    char ch[100];//格式化的日期
//    for (int i = 0; i < 100; i++)
//        cin >> a[i];
//    for (int i = 0; i < 100; i++)
//    {
//        if (a[i] != 2)   continue;
//        for (int j = i + 1; j < 100; j++)
//        {
//            if (a[j] != 0) continue;
//            for (int z = j + 1; z < 100; z++)
//            {
//                if (a[z] != 2)   continue;
//                for (int k = z + 1; k < 100; k++)
//                {
//                    if (a[k] != 3)   continue;
//                    for (int l = k + 1; l < 100; l++)
//                    {
//                        for (int p = l + 1; p < 100; p++)
//                        {
//                            for (int o = p + 1; o < 100; o++)
//                            {
//                                for (int u = o + 1; u < 100; u++)
//                                {
//                                    int month = a[l] * 10 + a[p]; //两位数月份
//                                    if (month <= 0 || month > 12)  continue;
//                                    int day = a[o] * 10 + a[u];
//                                    if (day < 1 || day > t[month]) continue;//最大不能超过当月最大日期，最小不能小于1
//                                    sprintf(ch, "%02d%02d", month, day);
//                                    st.insert(ch);
//                                }
//                            }
//                        }
//                    }
//                }
//            }
//        }
//    }
//    cout << st.size() << endl;
//    return 0;
//}





//											找出对于数字n的 1 - n 之间 的所有约数
//const int maxl = 1e5 + 7;
//int main() 
//{
//	int cnt = 0;
//	int a[maxl];
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n / i; i++) {//不是i * i <= n 原因： i * i可能超出整形范围 
//		if (n % i == 0) {
//			a[cnt++] = i;
//			if (i != n / i)	a[cnt++] = n / i;//这一行利用约数的性质，即可遍历一半的数求所有约数 
//		}
//	}
//	for (int i = 0; i < cnt; i++)	cout << a[i] << " ";
//	return 0;
//}






//signed main()
//{
//    // 请在此输入您的代码
//    int n = 0;
//    cin >> n;
//    vector<int> a(n), b(n);
//
//    for (int i = 0; i < n; i++)
//        cin >> a[i] >> b[i];
//
//    for (int i = 1; i < 1e6; i++) //V
//    {
//        bool r = true;
//        for (int j = 0; j < n; j++) //
//        {
//            if (b[j] != a[j] / i)
//            {
//                r = false;
//                continue;
//            }
//            else
//            {
//                cout << i << " ";
//                break;
//            }
//
//        }
//    }
//    for (int i = 1e6; i >= 1; i--)
//    {
//        bool r = true;
//        for (int j = n; j >= 0; j--) //
//        {
//            if (b[j] != a[j] / i)
//            {
//                r = false;
//                continue;
//            }
//            else
//            {
//                cout << i << " ";
//                break;
//            }
//
//        }
//    }
//    return 0;
//}







//#include <stack>
//class Solution
//{
//public:
//    bool isValid(string s)
//    {
//        int n = s.size();
//        if (n == 0 || n == 1)   return false;
//        if (s[0] == ')' || s[0] == ']' || s[0] == '}') return false;
//        stack<char> a;
//        //s[0]一定是'(' '[' '{'
//        a.push(s[0]);
//        for (int i = 1; i < n; i++)
//        {
//            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
//                a.push(s[i]);
//            else
//            {
//                if (s[i] == ')' && a.top() != '(')   return false;
//                if (s[i] == ']' && a.top() != '[')   return false;
//                if (s[i] == '}' && a.top() != '{')   return false;
//                if (!a.empty())  a.pop();
//                else {
//                    a.push(s[i]);
//                }
//            }
//        }
//        if (!a.empty())  return false;
//        return true;
//    }
//};
//
//
//int main()
//{
//    string s = "[])";
//    bool ret = Solution().isValid(s);
//    cout << ret;
//}

//#include <fstream>
//
//int main()
//{
//	std::string filename = "C:\\Users\\伊人\\Desktop\\Linux其他命令.txt";
//	std::ifstream f(filename);
//
//	if (!f.is_open())
//	{
//		std::cerr << "打开文件失败" << std::endl;
//		return -1;
//	}
//	std::string line;
//	while (std::getline(f, line))
//	{
//		std::cout << line << std::endl;
//	}
//	f.close();
//
//}

//class Solution
//{
//public:
//    string minWindow(string s, string t)
//    {
//        int hashs[128] = { 0 };
//        int hasht[128] = { 0 };
//        string ret(100001, ' ');
//        //把t中出现字符的对应次数存入哈希表
//        for (int i = 0; i < t.size(); i++)
//        {
//            hasht[t[i]]++;
//        }
//
//        for (int l = 0, r = 0; r < s.size(); r++)
//        {
//            //如果字符不在hasht里面
//            while (!hasht[s[r]])
//                r++;
//
//            hashs[s[r]]++;
//            //如果俩哈希相等，更新长度
//            if (equal_hash(hashs, hasht))
//            {
//                ret = minstr(ret, s.substr(l, r + 1));
//                hashs[s[l]]--;
//                l++;
//                while (l < s.size() && !hasht[s[l]])
//                    l++;
//            }
//        }
//
//        return ret;
//    }
//    string minstr(const string& s1, const string& s2)
//    {
//        return s1.size() < s2.size() ? s1 : s2;
//    }
//    bool equal_hash(int arr1[], int arr2[])
//    {
//        int sum1 = 0, sum2 = 0;
//        for (int i = 0; i < 128; i++)
//        {
//            sum1 += arr1[i];
//            sum2 += arr2[i];
//        }
//        if (sum1 == sum2)
//            return true;
//        return false;
//    }
//
//};
//
//
//int main()
//{
//    std::string ret = Solution().minWindow("ADOBECODEBANC", "ABC");
//    std::cout << ret << std::endl;
//}




//class Solution
//{
//public:
//    bool validPalindrome(string s)
//    {
//        int l = 0, r = s.size() - 1;
//        while (l < r)
//        {
//            if (s[l] == s[r])
//            {
//                l++;
//                r--;
//            }
//            else if (s[l] != s[r])
//            {
//                s.erase(l);
//                break;
//            }
//        }
//        l = 0, r = s.size() - 1;
//        while (l < r)
//        {
//            if (s[l] == s[r])
//            {
//                l++;
//                r--;
//            }
//            else
//            {
//                return false;
//            }
//        }
//        return true;
//    }
//};
//
//
//
//
//int main()
//{
//    string s = "a,b,c";
//    bool ret = Solution().validPalindrome(s);
//    cout << ret;
//}




//class Solution
//{
//public:
//    vector<int> spiralOrder(vector<vector<int>>& matrix)
//    {
//        vector<int> ret;
//        for (int k = 0, i = 0, j = 0; k < matrix.size(); k++, i = i + k, j = j + k)
//        {
//            while (j < matrix[k].size())
//                ret.push_back(matrix[i][j++]);
//            j = matrix[i].size() - 1;
//            i++;
//            while (i < matrix.size())
//                ret.push_back(matrix[i++][j]);
//            i = matrix.size() - k - 1;
//            j--;
//            while (j >= 0)
//                ret.push_back(matrix[i][j--]);
//            j = 0;
//            i--;
//            while (i!= k && i < matrix.size() - k)
//                ret.push_back(matrix[i--][j]);
//        }
//        return ret;
//    }
//};
//
//
//int main()
//{
//    vector<vector<int>> v{ {1,2,3 }, {4, 5, 6}, {7, 8, 9} };
//
//    vector<int> ret = Solution().spiralOrder(v);
//    for (auto e : ret)
//    {
//        cout << e << endl;
//    }
//}


//#include <stack>
//class MinStack {
//public:
//    stack<int> s;
//    stack<int> mins;
//    MinStack()
//    {
//
//    }
//
//    void push(int val) {
//        if (mins.empty())
//            mins.push(val);
//        else
//        {
//            int topn = mins.top();
//            if (val < topn)
//                mins.top() = val;
//        }
//        s.push(val);
//    }
//
//    void pop() {
//        if (!s.empty() && s.top() == mins.top())
//            mins.pop();
//        s.pop();
//    }
//
//    int top() {
//        if (!s.empty())
//            return s.top();
//        return 0;
//    }
//
//    int getMin() {
//        if (!mins.empty())
//            return mins.top();
//        return 0;
//    }
//};
//
//
//
//int main()
//{
//      /*MinStack* obj = new MinStack();
//      obj->push(-2);
//      obj->pop();
//      int param_3 = obj->top();
//      int param_4 = obj->getMin();*/
//    MinStack minStack;
//      minStack.push(-2);
//      minStack.push(0);
//      minStack.push(-3);
//      minStack.getMin();   
//          minStack.pop();
//      minStack.top();      
//          minStack.getMin();   
//}




//#include <stack>
//class Solution
//{
//public:
//    string decodeString(string s)
//    {
//        int n = s.size();
//        stack<int> s1;
//        stack<char> s2;
//        for (int i = 0; i < n; i++)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int tmp = 0;
//                for (int j = i; s[j] >= '0' && s[j] <= '9'; j++)
//                    tmp = tmp * 10 + s[j] - '0';
//                s1.push(tmp);
//            }
//            if ((s[i] >= 'a' && s[i] <= 'z') || s[i] == '[')
//                s2.push(s[i]);
//            string str;
//            if (s[i] == ']')
//            {
//                int num = s1.top(); s1.pop();
//                while (!s2.empty() && s2.top() != '[')
//                {
//                    str += s2.top(); s2.pop();
//                }
//                s2.pop();
//                reverse(str.begin(), str.end());
//                while (num--)
//                {
//                    for (auto& e : str)
//                        s2.push(e);
//                }
//            }
//        }
//        string ret;
//        while (!s2.empty())
//        {
//            ret += s2.top(); s2.pop();
//        }
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//
//
//};
//int main()
//{
//    string s = "100[leetcode]";
//    string ret = Solution().decodeString(s);
//    cout << ret.c_str() << endl;
//}

//class Solution
//{
//public:
//    int lengthOfLongestSubstring(string s)
//    {
//        if (s.size() == 0)
//            return 0;
//        int hash[50000];
//        int len = 0;
//        for (int l = 0, r = 0; r < s.size(); r++)
//        {
//            hash[s[r]]++;
//
//            while (hash[s[r]] > 1)
//            {
//                hash[s[l]]--;
//                l++;
//            }
//            len = max(len, r - l + 1);
//        }
//
//        return len;
//    }
//};
//
//int main()
//{
//    string s = "bb";
//    int ret = Solution().lengthOfLongestSubstring(s);
//    cout << ret;
//}

  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
  class Solution
  {
  public:
      ListNode* partition(ListNode* head, int x)
      {
          ListNode* root = new ListNode(0);
          ListNode* rtmp = root;
          while (head)
          {
              if (head->val >= x)
              {
                  ListNode tmp(head->val);
                  rtmp->next = &tmp;
                  rtmp = rtmp->next;
              }
              else
              {
                  ListNode tmp(head->val);
                  ListNode* t = root->next;
                  root->next = &tmp;
                  tmp.next = t;
              }
              head = head->next;
          }
          return root->next;
      }
  };

int main()
{
    ListNode head1(1);
    ListNode head2(4);
    ListNode head3(3);
    ListNode head4(2);
    ListNode head5(5);
    ListNode head6(2);
    head1.next = &head2;
    head2.next = &head3;
    head3.next = &head4;
    head4.next = &head5;
    head5.next = &head6;
    
    ListNode* ret = Solution().partition(&head1, 3);
    while (ret)
    {
        cout << ret->val << endl;
        ret = ret->next;
    }
}